package game;

/**
 * 给定一个正数1，裂开的方法有一种，(1)
 * 给定一个正数2，裂开的方法有两种，(1和1)、(2)
 * 给定一个正数3，裂开的方法有三种，(1、1、1)、(1、2)、(3)
 * 给定一个正数4，裂开的方法有五种，(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、(4)
 * 给定一个正数n，求裂开的方法数。
 * 动态规划优化状态依赖的技巧
 * 动态规划的斜率优化技巧：当表格中的一个值和很多表格的值相依赖，将这些多个表格的依赖替换为一个相邻表格的值（前提：这个相邻表格和我依赖的这些表格值有一对一的关系）
 *
 * @author Liaorun
 */
public class SplitNumber {

    public static void main(String[] args) {
        System.out.println(ways1(3));
        System.out.println(ways2(3));
        System.out.println(ways3(3));
    }

    /**
     * 递归版本，求解数字的裂开方式
     *
     * @param n
     * @return
     */
    public static int ways1(int n) {
        if (n < 1) {
            return 0;
        }

        // 主函数的传入参数，代表需要的是动态规划表上那个坐标的值
        return process(1, n);
    }

    /**
     * @param pre  裂开的前一部分
     * @param rest 还剩多少值，需要去裂开，要求裂出来的第一部分，不要比pre小
     * @return 返回裂开的方法数
     */
    private static int process(int pre, int rest) {
        if (rest == 0) {
            // 之前裂开的方案，构成了一种有效方法
            return 1;
        }
        if (pre > rest) {
            // 之前裂开的方案，构成不了一种有效方法
            return 0;
        }
        int ways = 0;
        // 尝试所有可能的裂开方法
        for (int i = pre; i <= rest; i++) {
            ways += process(i, rest - i);
        }

        return ways;
    }

    /**
     * 动态规划版本，求解数字的裂开方式
     *
     * @param n
     * @return
     */
    public static int ways2(int n) {
        if (n < 1) {
            return 0;
        }

        int[][] dp = new int[n + 1][n + 1];
        // 第一列全部填1，处理dp[0][0] 位置
        for (int pre = 1; pre < dp.length; pre++) {
            dp[pre][0] = 1;
        }

        // 动态规划从下往上
        for (int pre = n; pre > 0; pre--) {
            // 从没一行的对角线开始向右算
            for (int rest = pre; rest <= n; rest++) {
                for (int i = pre; i <= rest; i++) {
                    dp[pre][rest] += dp[i][rest - i];
                }
            }
        }

        return dp[1][n];
    }

    /**
     * 动态规划 + 斜率优化版本，求解数字的裂开方式
     *
     * @param n
     * @return
     */
    public static int ways3(int n) {
        if (n < 1) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1];

        // 第一列除了dp[0][0]全为1
        for (int pre = 1; pre < dp.length; pre++) {
            dp[pre][0] = 1;
        }

        // 对角线除了dp[0][0]全为1
        for (int pre = 1; pre < dp.length; pre++) {
            dp[pre][pre] = 1;
        }

        for (int pre = n - 1; pre > 0; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
            }
        }
        return dp[1][n];
    }
}
